package com.zhang.graph.directedgraph;


import java.util.*;

/**
 * @author zhang
 * @time 2022/03/20 11:24:17
 */
class Item{
    private String name;

    public Item(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Item item = (Item) o;
        return name.equals(item.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name);
    }
}
public class Graph01 {
    private class Node {
        private String label;
        private List<Edge> edges = new ArrayList<>();

        public Node(String label) {
            this.label = label;
        }

        @Override
        public String toString() {
            return label;
        }

        public void addEdge(Node to) {
            edges.add(new Edge(this, to));
        }
        public void removeEdge(Node to) {
            edges.remove(new Edge(this, to));
        }

        public List<Edge> getEdges() {
            return edges;
        }
    }
    private class Edge{
        private Node from;
        private Node to;

        public Edge(Node from, Node to) {
            this.from = from;
            this.to = to;
        }

        @Override
        public String toString() {
            return from + "->" + to;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge edge = (Edge) o;
            return from.label.equals(edge.from.label) && to.label.equals(edge.to.label);
        }

        @Override
        public int hashCode() {
            return Objects.hash(from, to);
        }
    }

    private Map<String, Node> nodes = new HashMap<>();

    public void addNode(String label) {
        nodes.putIfAbsent(label, new Node(label));
    }

    public void addEdge(String from, String to) {
        Node fromNode = nodes.get(from);
        if (fromNode == null) {
            throw new IllegalArgumentException();
        }

        Node toNode = nodes.get(to);
        if (toNode == null) {
            throw new IllegalArgumentException();
        }

        fromNode.addEdge(toNode);

    }

    public void removeNode(String label) {
        Node node = nodes.get(label);
        if (node == null) {
            return;
        }
        for (Node node1 : nodes.values()) {
            node1.removeEdge(node);
        }
        nodes.remove(label);

    }

    public void removeEdge(String from, String to) {
        Node fromNode = nodes.get(from);
        if (fromNode == null) {
            throw new IllegalArgumentException();
        }

        Node toNode = nodes.get(to);
        if (toNode == null) {
            throw new IllegalArgumentException();
        }

        fromNode.removeEdge(toNode);
    }
    public void print() {
        for (Node node : nodes.values()) {
            List<Edge> edges = node.getEdges();
            if (!edges.isEmpty()) {
                System.out.println(node + " is connected to " + edges);
            }

        }
    }
    public void traverseDepthFirstRec(String root) {
        Node node = nodes.get(root);
        if (node == null) {
            return;
        }

        traverseDepthFirstRec(node, new HashSet<Node>());
    }

    private void traverseDepthFirstRec(Node root, HashSet<Node> visited) {
        System.out.println(root);
        visited.add(root);

        for (Edge edge : root.getEdges()) {
            if (!visited.contains(edge.to)) {
                traverseDepthFirstRec(edge.to, visited);
            }
        }
    }

    public void traverseDeptFirst(String root) {
        Node node = nodes.get(root);
        if (node == null) {
            return;
        }

        HashSet<Node> visited = new HashSet<>();
        Stack<Node> stack = new Stack<>();

        stack.push(node);

        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            if (visited.contains(pop)) {
                continue;
            }
            System.out.println(pop);
            visited.add(pop);

            for (Edge edge : pop.getEdges()) {
                if (!visited.contains(edge.to)) {
                    stack.push(edge.to);
                }
            }
        }
        
    }
    public void traverseBreadthFirst(String root) {
        Node node = nodes.get(root);

        if (node == null) {
            return;
        }
        Set<Node> visited = new HashSet<>();
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node current = queue.remove();

            if (!visited.contains(current)) {
                continue;
            }
            System.out.println(current);
            visited.add(current);

            for (Edge edge : current.getEdges()) {
                if (visited.contains(edge.to)) {
                    queue.add(edge.to);
                }
            }
        }
    }
    public List<String> topologicalSort() {
        Stack<Node> stack = new Stack<>();
        Set<Node> visited = new HashSet<>();

        for (Node node : nodes.values()) {
            topologicalSort(node,visited,stack);
        }

        List<String> sorted = new ArrayList<>();
        while (!stack.empty()) {
            sorted.add(stack.pop().label);
        }
        return sorted;


    }

    private void topologicalSort(Node node, Set<Node> visited, Stack<Node> stack) {
        if (visited.contains(node)) {
            return;
        }
        visited.add(node);
        for (Edge edge : node.getEdges()) {
            topologicalSort(edge.to, visited, stack);
        }
        stack.push(node);
    }

    public boolean hasCycle() {
        Set<Node> all = new HashSet<>();
        all.addAll(nodes.values());

        Set<Node> visiting = new HashSet<>();
        Set<Node> visited = new HashSet<>();

        while (!all.isEmpty()) {
            Node current = all.iterator().next();
            if (hasCycle(current, all, visiting, visited)) {
                return true;
            }
        }
        return false;

    }

    private boolean hasCycle(Node node, Set<Node> all, Set<Node> visiting, Set<Node> visited) {
        all.remove(node);
        visiting.add(node);

        for (Edge edge : node.getEdges()) {
            if (visited.contains(edge.to)) {
                continue;
            }
            if (visiting.contains(edge.to)) {
                return false;
            }
            if (hasCycle(edge.to, all, visiting, visited)) {
                return false;
            }
        }
        visiting.remove(node);
        visited.add(node);
        return false;
    }

    public static void main(String[] args) {
        Graph01 g = new Graph01();
        g.addNode("A");
        g.addNode("B");
        g.addNode("C");
        g.addNode("D");
        g.addNode("E");


        g.addEdge("A","B");
        g.addEdge("B","C");
        g.addEdge("B","D");
        g.addEdge("D","C");
        g.addEdge("A","E");
        g.print();

        g.traverseDeptFirst("A");


    }


}
